package com.leetcode.No0777;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: leetcode
 * @description: 在LR字符串中交换相邻字符
 * @author: wangzhihua
 * @date: 2022-10-18
 */
public class Solution2 {
	public boolean canTransform(String start, String end) {
		char[] startChs = moveStr(start.toCharArray());
		char[] endChs = moveStr(end.toCharArray());

		System.out.println(Arrays.toString(startChs));
		System.out.println(Arrays.toString(endChs));

		processChs(startChs);
		processChs(endChs);

		System.out.println(Arrays.toString(startChs));
		System.out.println(Arrays.toString(endChs));

		return checkEqual(startChs, endChs);
	}

	public char[] moveStr(char[] chars) {
		int len = chars.length;

		int left = 0, right = len - 1;
		while (left < len || right >= 0) {
			int tempLeft = left;
			int tempRight = right;

			while (tempLeft < len && chars[tempLeft] == 'X') {
				++tempLeft;
			}
			while (tempRight >= 0 && chars[tempRight] == 'X') {
				--tempRight;
			}

			if (tempLeft < len && chars[tempLeft] == 'L') {
				chars[tempLeft] = 'X';
				chars[left] = 'L';
			}
			if (tempRight >= 0 && chars[tempRight] == 'R') {
				chars[tempRight] = 'X';
				chars[right] = 'R';
			}

			left = tempLeft + 1;
			right = tempRight - 1;
		}
		return chars;
	}

	public void processChs(char[] chs) {
		int len = chs.length;

		int idx = 0;
		while (idx < len) {
			while (chs[idx] == 'X') {
				++idx;
			}
			if (chs[idx] == 'R') {
				++idx;
				continue;
			}
			while (++idx < len && chs[idx] == 'X') {
				chs[idx] = 'Y';
			}
		}

		idx = len - 1;
		while (idx >= 0) {
			while (chs[idx] == 'X') {
				--idx;
			}
			if (chs[idx] == 'L') {
				--idx;
				continue;
			}
			while (--idx >= 0 && chs[idx] == 'X') {
				chs[idx] = 'Y';
			}
		}
	}

	public boolean checkEqual(char[] chs1, char[] chs2) {
		int len = chs1.length;
		int idx1 = -1, idx2 = -1;
		while (true) {
			while (++idx1 < len && chs1[idx1] == 'Y') {}
			while (++idx2 < len && chs2[idx2] == 'Y') {}
			if (idx1 >= len || idx2 >= len) {
				break;
			}
			if (chs1[idx1] != chs2[idx2]) {
				return false;
			}
		}

		int idx = Math.min(idx1, idx2);
		if (idx >= len) {
			return true;
		}

		char[] chs = (idx == idx1 ? chs1 : chs2);
		while (idx < len) {
			if (chs[idx] != 'Y') {
				return false;
			}
			++idx;
		}
		return true;
	}

	@Test
	public void test1() {
		String start = "RXXLRXRXL";
		String end = "XRLXXRRLX";
//		System.out.println(this.canTransform(start, end));

		start = "RXXLRXRXLX";
		end = "XRLXXRRLXX";
//		System.out.println(this.canTransform(start, end));

		start = "RXXXXXLRXRXLX";
		end = "XRXLXLXXRRLXX";
//		System.out.println(this.canTransform(start, end));

		start = "X";
		end = "L";
//		System.out.println(this.canTransform(start, end));

		start = "XLLR";
		end =   "LXLX";
//		System.out.println(this.canTransform(start, end));

		// false
		start = "LXXLXRLXXL";
		end =   "XLLXRXLXLX";
		System.out.println(this.canTransform(start, end));

		// true
		start = "RXXLRXRXL";
		end =   "XRLXXRRLX";
//		System.out.println(this.canTransform(start, end));

		// true
		start = "XXXXXLXXXX";
		end =   "LXXXXXXXXX"; 
//		System.out.println(this.canTransform(start, end));
	}
}
